HashMap 源码分析

概念

下图可从可视化的角度理解 HashMap（其实也是方便自己想起来）。

常量与重要的成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 默认容量(也是最小容量阈值)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量阈值
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 从链表转变为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 从红黑树转变为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 从链表转变为红黑树的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

// HashMap 实际存储键值对的容器
transient Node<K,V>[] table;
// HashMap 实际阈值，其值由 capacity * loadFactor 决定
int threshold;

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public HashMap(int initialCapacity, float loadFactor) {
  	if (initialCapacity < 0)
    	throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  	if (initialCapacity > MAXIMUM_CAPACITY)
    	initialCapacity = MAXIMUM_CAPACITY;
  	if (loadFactor <= 0 || Float.isNaN(loadFactor))
    	throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  	this.loadFactor = loadFactor;
  	// 重点！
  	this.threshold = tableSizeFor(initialCapacity);
}

// 该方法用于返回大于给定容量的最小2的幂次方的数值
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

为什么 HashMap 的容量数值非要是2的幂次方呢？请看JDK 源码中 HashMap 的 hash 方法原理是什么？

hash()

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap 中的实际 hash 值计算是通过 key.hashCode()所得出来的h ，与h无条件右移16位后，进行按位异或^得出来的。

但是怎么转化成实际上table数组的所索引值呢？剧透一下，table 的索引值是通过 capacity与hash进行按位与&计算出来的。

putVal()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
  	// 当HashMap中的数组，即table为空，或者table的长度为0时，调用 resize 方式进行 HashMap 的初始化(HashMap真正的容器初始化阶段是在第一次插入时)
  	if ((tab = table) == null || (n = tab.length) == 0)
       	n = (tab = resize()).length;
   	
  	// 根据n(capacity)-1与hash值进行按位运算，获得该key值对应的数组中的位置。若该索引(p)上的值为null，则直接创建新的节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
  
  	// 该索引上的值不为null，那么需要分以下三种情况分析
    else {
        Node<K,V> e; K k;
      
      	// 该p的hash值与传入的hash值相等，并且p的key值也与传入的key值相等，或者在hash值不相同的情况下，两者的key值是相同的
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
      
      	// 若p的key值不等于传入的key值
      	// p的类型属于TreeNode，即从属于红黑树，则转由红黑树进行实际节点添加的操作
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      	// p的类型属于Node，即从属于链表。这里就是HashMap中怎么处理哈希冲突的办法。
      	// 当传入元素的hash值与数组上的元素相同，但key不同时。
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
      
      	// 当上述的添加新节点的阶段结束后，若此时的e(即原始节点)不为空时，则进行值的替换。
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
  	
    ++modCount;	// 用于记录修改的操作次数
	// 若此时的容器容量大于阈值时，进行resize()扩容容器
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 如果看懂了putVal()，那么get()就是同样的方式分析了
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

resize()

resize()实际上的目的在于将原数组中的值均匀地平摊到新数组中，这样无论是插入还是访问的效率也会有一定的提升。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// 这一部分分析难度不亚于putVal()
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
  
  	// 若老数组为0，那么老容量为0，否则为老数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
  
  	// 若老容量大于0
    if (oldCap > 0) {
      	// 若老容量是否大于最大容量阈值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
      	// 若扩容后的新容量小于最大容量阈值且老容量大于默认容量值，则新阈值为老阈值的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
  
  	// 若老容量等于0且老阈值大于0，那么新容量就等于老阈值
    else if (oldThr > 0)
        newCap = oldThr;
  	// 若老容量等于0且老阈值也为0，这种比较极端了
  	// 新容量为默认容量值，而新阈值也为默认阈值(0.75)
    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
  
  	// 若新阈值为0，那么则由负载因子与新容量的乘积获得
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
  
  	// 实际操作部分，初始化新容器！
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
  	
  	// 其实HashMap的初始化阶段从这里就结束了，以下部分只适用于存有实际节点的容器
    if (oldTab != null) {
      	// 遍历老数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
          	// 若该索引上的节点部位不为空，则分以下三种情况分析
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
              	// 单个节点
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
              	// 红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
              	// 链表
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
  
    return newTab;
}

实际可视化操作如下所示：

为什么 HashMap 不是线程安全的？

根据《Java并发编程的艺术》中写道：

HashMap 在并发执行 put 操作时会引起死循环，导致 CPU 利用率接近100%。因为多线程会导致 HashMap 的 Node 链表形成环形数据结构，一旦形成环形数据结构，Node 的 next 节点永远不为空，就会在获取 Node 时产生死循环。

实际原理可以疫苗：JAVA HASHMAP的死循环一文。